Viterbi decoding, also known as maximum likelihood decoding and forward dynamic programming, is one method for decoding convolutional codes. Viterbi decoding finds a sequence of bits that is closest to an actual received sequence. The Viterbi algorithm uses the redundancy imparted by a convolutional encoder to decode the bit stream and remove errors. Viterbi decoding uses an asymptotically optimum decoding technique. The decoding technique is based on the assumption that a channel is memory-less, therefore there are a finite number of possible states in a decoder, and that given two consecutive states the input bits that cause a state transition between the two consecutive states can be predicted. By creating a trellis of possible states and possible state transitions, a path through the trellis could be traced back based on information such as branch metrics and state metrics and the encoded data can be decoded.
Viterbi decoders of the past, however, suffered various drawbacks. For example, in order to address state metric storage overflow, Viterbi decoders of the past typically normalized the state metrics using traditional division techniques. Using traditional division techniques to normalize state metrics, however, proved to be problematic because these techniques required approximation and introduced errors in state metric calculations. In addition, past Viterbi decoders performed traceback from a state of an encoder having the largest state metric at a time period. In order to determine the state of an encoder with the largest state metric, the Viterbi decoders utilized a pyramid of comparators and selectors that typically required a large number of logical elements. These decoders suffered the drawback of being too large and expensive for many applications. The decoders also suffered the drawback of constraining routing due to the wide paths required for implementing comparison trees.
Thus, what is needed is an efficient and effective method and apparatus for implementing a Viterbi decoder for decoding convolutional codes.